package com.arron.algorithm;

import java.util.ArrayList;

/**
 * @Classname FindNumbersWithSum
 * @Date 2020/9/13 16:11
 * @Created by 刘
 *
 * 题目：在一个递增的数组中，输入一个数s,在数组中找到2个数的和等于s，
 *      如果数组中有多对这样的数，则输出，2个数的乘积最小的那对数
 *      小的输出在前，大的输出在后。
 */
public class FindNumbersWithSum {

    public static void main(String[] args) {
        int[] a = {1,3,4,5,6,7,8};
        String str ="10.0.3.193";
        for (String s : str.split("\\.")) {
            System.out.println(s);
        }


    }

    /**
     * 找出数组中的2个和为sum的数对
     * @param array
     * @param sum
     * @return
     */
    public static ArrayList<Integer> find(int[] array,int sum){
        //定义2个指针,一个头指针，一个尾指针
        int i = 0;
        int j = array.length-1;
        ArrayList<Integer> list = new ArrayList<>();
        while (i<j){
            //如果直接匹配，那就是最小,因为已经排序
            if (array[i]+array[j] == sum){
                list.add(array[i]);
                list.add(array[j]);
                return list;
            }
            //如果没有匹配,就分两种情况，一种大于sum，一种小于sum
            while (i<j&&(array[i]+array[j])>sum) --j;
            while (i<j&&(array[i]+array[j])<sum) ++i;
        }

        //如果没找到，就直接返回
        return list;
    }

}
